1. Field of the Invention
The present invention relates to an automatic arrangement method and an automatic arrangement system in which arrangement knowledge of a plurality of composing elements is automatically obtained from past arrangement examples of the composing elements to determine an optimum (or appropriate) arrangement of the composing elements according to the arrangement knowledge of the composing elements. Also, the present invention relates to a recording medium in which a computer program indicating an automatic arrangement of a plurality of composing elements is recorded to perform the automatic arrangement of the composing elements in a computer.
2. Description of the Related Art
In cases where the number of composing elements is small and restriction for the composing elements is simple, the automatic arrangement of the composing elements can be easily performed. However, in cases where the number of composing elements is large and restriction for the composing elements is complicated, because it is difficult to automatically arrange the composing elements in an appropriate arrangement, the composing elements are manually arranged by a skilled person. As an example of the arrangement of composing elements, the arrangement of composing parts on a printed circuit board (PCB) is known. In this arrangement, an automatic parts arrangement system is used for the composing parts. However, because it is difficult to appropriately arrange the composing parts, the composing parts are manually arranged by a skilled person.
As an example of the automatic parts arrangement system, an automatic parts arrangement system (H. Yoshimura, S. Miura xe2x80x9cApproach from Artificial Intelligence to CAD of the PCB Designxe2x80x9d the 10th Annual Conference of JSAI, 1996) is known. In this system, knowledge of composing parts arrangement is extracted from a skilled person by interviewing with the skilled person, the extracted knowledge is reflected on the automatic parts arrangement system, and a plurality of composing parts are automatically arranged on a PCB.
Also, a published unexamined Japanese Patent Application No. H5-342290 xe2x80x9cMETHOD AND DEVICE FOR ARRANGING ELEMENTSxe2x80x9d is disclosed. In this application, attraction and repulsion occurring between elements are calculated, and the position of each element is changed for each minute time according to a sum of the attraction and the repulsion.
However, even though a plurality of composing parts are automatically arranged on a PCB while reflecting knowledge extracted from a skilled person on the automatic parts arrangement system, there is a problem that the arrangement of the composing parts satisfying the skilled person cannot be always obtained. That is, the skilled person has knowledge unconsciously used as well as knowledge consciously used, the knowledge consciously used cannot be extracted by interviewing with the skilled person, so that the knowledge extracted from the skilled person are not sufficient to appropriately arrange the composing parts on the PCB. In particular, because a density of wirings on the PCB and a density of parts attached on the printing substrate have been recently heightened, there is little space between the composing parts on the PCB, it is required that the skilled person performs the trial and error operation many times to appropriately arrange the composing parts on the PCB. Therefore, the knowledge of the skilled person has been more complicated, so that the extraction of the knowledge from the skilled person becomes more difficult. As a result, the composing parts cannot be appropriately arranged on the PCB in a conventional automatic arrangement system according to a conventional automatic arrangement method performed by extracting the knowledge of the parts arrangement from the skilled person.
Also, in cases where elements are arranged according to the method and device for arranging elements disclosed in the published unexamined Japanese Patent Application No. H5-342290, it is required that a function for calculating the attraction and repulsion is prepared in advance, so that there is a problem that a technical knowledge is required for an element arrangement designer to determine the function.
An object of the present invention is to provide, with due consideration to the drawbacks of such a conventional automatic arrangement method and a conventional automatic arrangement system, an automatic arrangement method and an automatic arrangement system in which positions of a plurality of composing elements are automatically set in an optimum (or appropriate) arrangement without extracting knowledge of element arrangement from a skilled person.
Also, the object is to provide a recording medium for recording a computer program indicating the automatic arrangement method.
The object is achieved by the provision of an automatic arrangement method, comprising the steps of:
preparing a plurality of past examples respectively indicating a past arrangement of a set of composing elements, each past example of composing elements being composed of position information indicating positions of the composing elements and attribute information indicating attributes of the composing elements;
preparing a potential function indicating a potential energy of one composing element;
selecting a plurality of particular past examples corresponding to a plurality of particular composing elements from the past examples;
automatically determining values of one or more parameters included in the potential function according to the particular past examples for each particular composing element;
differentiating each of the potential functions to obtain a force exerted on each particular composing element;
changing a position of each particular composing element according to the force to decrease a total potential energy obtained by summing up the potential energies of the particular composing elements, each potential energy of one particular composing element being obtained by determining a position of the particular composing element in one potential function; and
setting a particular arrangement of the composing elements placed at the changed positions.
In the above steps, in cases where a plurality of particular composing elements are arranged to minimize a sum of a plurality of potential energies obtained by solving a plurality of potential functions corresponding to the particular composing elements, positions of the particular composing elements are set in an optimum (or appropriate) arrangement. Because parameters included in each potential function are automatically determined according to the particular past examples, it is not required to extract knowledge of element arrangement from a skilled person for the purpose of setting the particular composing elements in an optimum arrangement.
Also, because a force exerted on each particular composing element is obtained by differentiating each potential function and a position of each particular composing element is changed according to the force to decrease the sum of the potential energies, the positions of the particular composing elements can be set in an optimum arrangement.
The object is also achieved by the provision of an automatic arrangement method, comprising the steps of:
preparing a plurality of past examples respectively indicating a past arrangement of a set of composing elements, each past example of one set of composing elements being composed of past position information indicating past positions of the composing elements, past attribute information indicating attributes of the composing elements and past connection information indicating a direct connection of each composing element with other composing elements or another composing element;
preparing a prototype of a total potential function indicating a total potential energy of a plurality of composing elements in a potential field made by the composing elements;
inputting particular element information of a plurality of particular composing elements, the particular element information being composed of particular attribute information indicating attributes of the particular composing elements and particular connection information indicating a direct connection of each particular composing element with other particular composing elements or another particular composing element;
selecting a plurality of particular past examples corresponding to the particular composing elements from the past examples, the particular past examples being composed of particular past position information of the particular composing elements, particular past attribute information of the particular composing elements and particular past connection information of the particular composing elements;
producing a total past potential function corresponding to the particular composing elements from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples;
setting values of one or more parameters include in the total past potential function as a set of parameter values;
calculating a total past potential energy of the particular composing elements from the total past potential function by giving one set of parameter values to the total past potential function to determine an equation of the total past potential function and giving particular past positions of the particular composing elements indicated by the particular past position information of the particular past examples to the equation of the total past potential function to solve the equation of the total past potential function each time the set of parameter values is set while changing the parameter values;
determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized;
producing a total potential function corresponding to the particular composing elements from the prototype of the total potential function according to the particular attribute information and the particular connection information of the particular element information;
giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function;
determining a particular set of positions of the particular composing elements on condition that a particular total potential energy of the particular composing elements obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function; and
adopting a particular arrangement of the particular composing elements determined by the particular set of positions of the particular composing elements as an optimum arrangement of the particular composing elements.
The object is also achieved by the provision of an automatic arrangement system, comprising:
past example storing means for storing a plurality of past examples respectively indicating a past arrangement of a set of composing elements, each past example of one set of composing elements being composed of past position information indicating past positions of the composing elements, past attribute information indicating attributes of the composing elements and past connection information indicating a direct connection of each composing element with other composing elements or another composing element;
total potential function storing means for storing a prototype of a total potential function indicating a total potential energy of a plurality of composing elements in a potential field made by the composing elements;
element information receiving means for receiving particular element information of a plurality of particular composing elements, the particular element information being composed of particular attribute information indicating attributes of the particular composing elements and particular connection information indicating a direct connection of each particular composing element with other particular composing elements or another particular composing element;
past example selecting means for selecting a plurality of particular past examples corresponding to the particular composing elements received by the element information receiving means from the past examples stored in the past example storing means, the particular past examples being composed of particular past position information of the particular composing elements, particular past attribute information of the particular composing elements and particular past connection information of the particular composing elements;
parameter value determining means for producing a total past potential function corresponding to the particular composing elements received by the element information receiving means from the prototype of the total potential function stored in the total potential function storing means according to the particular past attribute information and the particular past connection information of the particular past examples, setting values of one or more parameters included in the total past potential function as a set of parameter values each time the parameter values are changed, determining an equation of the total past potential function by giving one set of parameter values to the total past potential function, calculating a total past potential energy of the particular composing elements from the equation of the total past potential function by giving particular past positions of the particular composing elements indicated by the particular past position information of the particular past examples to the equation of the total past potential function each time the parameter values are changed, and determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized; and
optimum arrangement determining means for producing a total potential function corresponding to the particular composing elements received by the element information receiving means from the prototype of the total potential function stored in the total potential function storing means according to the particular attribute information and the particular connection information of the particular element information received by the element information receiving means, giving the particular set of parameter values determined by the parameter value determining means to the total potential function to determine a particular equation of the total potential function, determining a particular set of positions of the particular composing elements on condition that a particular total potential energy of the particular composing elements obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function, and adopting a particular arrangement of the particular composing elements determined by the particular set of positions of the particular composing elements as an optimum arrangement of the particular composing elements.
In the above steps and configuration, because a plurality of particular past examples corresponding to a plurality of particular composing elements specified by an operator are selected from the past examples and a particular set of parameter values to be given to a total potential function is determined according to the particular past examples, it is not required to extract knowledge of element arrangement from a skilled person for the purpose of setting the particular composing elements in an optimum (or appropriate) arrangement.
Also, because a total potential energy of the particular composing elements is calculated from the total potential function by giving the particular set of parameter values and particular element information input by the operator to the total potential function, an optimum arrangement of the particular composing elements can be automatically set on condition that the particular composing elements are arranged to minimize the total potential energy.
The object is also achieved by the provision of a recording medium for recording a computer program indicating an automatic arrangement of a plurality of composing elements to perform the automatic arrangement of the composing elements in a computer by reading out the computer program from the recording medium, the computer program comprises the steps of:
automatically determining values of one or more parameters included in a potential function corresponding one composing element according to a past arrangement example for each composing element;
differentiating each potential function to obtain a force exerted on each composing element;
changing a position of each composing element according to the force to decrease a total potential energy of the composing elements; and
setting a particular arrangement of the composing elements placed at the changed positions.
In the above recording medium, because a computer program indicating the automatic arrangement method is recorded, when the computer program is read out from the recording medium in a computer, the composing elements can be set to an optimum arrangement.
Also, the object is achieved by the provision of an automatic arrangement method, comprising the steps of:
determining an arranging order of a plurality of composing elements in a first classifier system according to attributes of the composing elements and one or more connection conditions among the composing elements;
determining an arranging position determining method for each composing element in the arranging order of the composing elements in a second classifier system according to the attributes of the composing elements and the connection conditions among the composing elements;
determining an arranged position of each composing element in an arrangement area or an area surrounding the arrangement area according to the arranging position determining method determined for the composing element in the arranging order of the composing elements;
judging in a third classifier system whether or not the change of the arranged position of each composing element is required according to the attributes and arranged positions of the composing elements and the connection conditions among the composing elements in the arranging order of the composing elements;
detecting a position changing method for one composing element in the third classifier system in cases where it is judged that the change of the arranged position of the composing element is required; and
changing the arranged position of one composing element according to the position changing method for the composing element, in cases where it is judged that the change of the arranged position of the composing element is required, to set the arranged positions of the composing elements in an optimum arrangement in the arrangement area.
The object is also achieved by the provision of an automatic arrangement system, comprising:
element information receiving means for receiving element information indicating a plurality of composing elements;
composing element storing means for storing one or more attributes of each composing element received by the element information receiving means;
composing element arranging order determining means, having a first classifier system, for determining an arranging order of the composing elements received by the element information receiving means in the first classifier system according to the attributes of the composing elements stored in the composing element storing means;
arranging position determining means, having a second classifier system, for determining an arranging position determining method for each composing element in the arranging order of the composing elements in the second classifier system according to the attributes of the composing elements and determining an arranged position of each composing element in an arrangement area or an area surrounding the arrangement area according to the arranging position determining method determined for the composing element in the arranging order of the composing elements;
arranged position change judging means, having a third classifier system, for judging in the third classifier system whether or not the change of the arranged position of each composing element is required according to the attributes and arranged positions of the composing elements in the arranging order of the composing elements and producing a position changing method for one composing element in the third classifier system in cases where it is judged that the change of the arranged position of the composing element is required; and
composing element arranging means for changing the arranged position of one composing element according to the position changing method for the composing element, in cases where it is judged in the third classifier system that the change of the arranged position of the composing element is required, to set the arranged positions of the composing elements in an optimum arrangement in the arrangement area.
In the above steps and configuration, an arranging order of a plurality of composing elements is determined in the first classifier system. Thereafter, an arranging position determining method of each composing element is determined in the second classifier system in the arranging order, an arranged position of each composing element is determined according to the arranging position determining method in the arranging order, and whether or not the change of the arranged position of each composing element is required is judged in the third classifier system in the arranging order, and the arranged position of one composing element is changed according to a position changing method in cases where the change of the arranged position of the composing element is required.
Accordingly, the arranged positions of the composing elements can be set in an optimum arrangement in the arrangement area without extracting knowledge of element arrangement from a skilled person.
The object is also achieved by the provision of a recording medium for recording a computer program indicating an automatic arrangement of a plurality of composing elements to perform the automatic arrangement of the composing elements in a computer by reading out the computer program from the recording medium, the computer program comprises the steps of:
determining an arranging order of a plurality of composing elements in a first classifier system according to attributes of the composing elements and one or more connection conditions among the composing elements;
determining an arranging position determining method for each composing element in the arranging order of the composing elements in a second classifier system according to the attributes of the composing elements and the connection conditions among the composing elements;
determining an arranged position of each composing element in an arrangement area or an area surrounding the arrangement area according to the arranging position determining method determined for the composing element in the arranging order of the composing elements;
judging in a third classifier system whether or not the change of the arranged position of each composing element is required according to the attributes and arranged positions of the composing elements and the connection conditions among the composing elements in the arranging order of the composing elements;
detecting a position changing method for one composing element in the third classifier system in cases where it is judged that the change of the arranged position of the composing element is required; and
changing the arranged position of one composing element according to the position changing method for the composing element, in cases where it is judged that the change of the arranged position of the composing element is required, to set the arranged positions of the composing elements in an optimum arrangement in the arrangement area.
In the above recording medium, because a computer program indicating the automatic arrangement method is recorded, when the computer program is read out from the recording medium in a computer, the composing elements can be set to an optimum arrangement.